package Compation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * 1329. 将矩阵按对角线排序
 * 给你一个 m * n 的整数矩阵 mat ，请你将同一条对角线上的元素（从左上到右下）按升序排序后，返回排好序的矩阵。
 * 示例 1：
 * 输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
 * 输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
 *
 * 提示：
 *
 * m == mat.length
 * n == mat[i].length
 * 1 <= m, n <= 100
 * 1 <= mat[i][j] <= 100
 */
public class diagonalSort {
    /**
     *
     * @param mat 输入矩阵
     * @return 排序后矩阵
     */
    public int[][] diagonalSort(int[][] mat) {
        if (mat == null || mat.length == 0) {
            return null;
        }
        int row = mat.length;
        int col = mat[0].length;
        int[][] result = new int[row][col];
        for (int i = 0; i < col; i++) {
            int r = 0;
            int j = 0;
            ArrayList<Integer> temp = new ArrayList<>();
            while (i + j < col && r + j < row) {
                temp.add(mat[r + j][i + j]);
                j++;
            }
            Collections.sort(temp);
            j = 0;
            while (i + j < col && r + j < row) {
                result[r + j][i + j] = temp.get(j);
                j++;
            }
        }

        for (int i = 1; i < row; i++) {
            int c = 0;
            int j = 0;
            ArrayList<Integer> temp = new ArrayList<>();
            while (i + j < row && c + j < col) {
                temp.add(mat[i + j][c + j]);
                j++;
            }
            Collections.sort(temp);
            j = 0;
            while (i + j < row && c + j < col) {
                result[i + j][c + j] = temp.get(j);
                j++;
            }
        }
        return result;
    }
}
